Golang源码-sort

Golang sort包相对独立，并且能帮助理解和使用golang中的interface

interface

Golang的interface可以说是开放的，不同于java，集成了interface，就要实现其所有的方法。就用Golang官网的例子来说明吧，为了方便阅读，我简化了下原本例子

在看例子之前，我们先看下源码对Interface的定义，其实只有3个方法，长度，大小，交换

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

例子，实现sort.Interface定义的3个方法

package main

import (
    "sort"
)

// 定义类
type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

type ByAge []Person

// 实现源码中的3个方法
func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func main() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    println(people)

    // ByAge集成了sort.Interface
    // 所以可以使用sort.的Sort方法
    sort.Sort(ByAge(people))
    println(people)
}

以下是通过学习源码，个人复现和说明

二分查找

思路：先定位中间位置 index，如果 fn(index) == true, 就移动j 到index，如果fn(index) == false，就移动I到index+1位置

func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := i + (j-i)/2 // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}

堆排序

思路:

step1 - 先对数组建大顶堆(假设按从大到小排列)
step2 - 然后将堆顶的数放置数组的末尾
step3 - 对数组0 ~ len-1重复step1和2，直到遍历完数组

func siftDown(data *[]int, lo, hi int) {
    index := lo
    for {
        // index的左儿子
        child := 2*index + 1
        if child >= hi {
            break
        }
        // 在左右儿子中找到大的那一个
        if child+1 < hi && (*data)[child] < (*data)[child+1] {
            child++
        }
        // 如果父比大的那一个儿子大，就结束
        if (*data)[index] > (*data)[child] {
            break
        }
        // 否则就把父和较大的儿子替换
        (*data)[index], (*data)[child] = (*data)[child], (*data)[index]
        // 位置替换成大儿子的
        index = child
    }
}

func heapSort(data *[]int) {
    hi := len(*data)

    // 建堆
    for i := (hi - 1) / 2; i >= 0; i-- {
        siftDown(data, i, hi)
    }

    for i := hi - 1; i >= 0; i-- {
        // 堆顶是最大的值，放到最末尾，长度-1后继续建堆
        (*data)[0], (*data)[i] = (*data)[i], (*data)[0]
        siftDown(data, 0, i)
    }
}